'''
从斐波那契数列看动态规划
    斐波那契数列: Fn = Fn-1 + Fn-2
    练习:使用递归和非递归的方法求解斐波那契数列的第n项
'''


def feibo(n):
    # 处理特殊情况
    if n <= 0:
        return []
    elif n == 1:
        return [1]
    elif n == 2:
        return [1, 1]

    # 标准斐波那契数列初始值
    li = [1, 1]
    for i in range(2, n):
        Fi = li[i - 1] + li[i - 2]
        li.append(Fi)
    return li


print(feibo(7))  # 输出: [1, 1, 2, 3, 5, 8, 13]

def fibonacci(n):
    if n <= 0:
        return []
    elif n == 1:
        return [1]
    elif n == 2:
        return [1, 1]
    else:
        fibo_li = fibonacci(n - 1)
        fibo_li.append(fibo_li[-1] + fibo_li[-2])
        return fibo_li

print(fibonacci(7))

def fibonacci_list(n):
    """
    递归生成斐波那契数列列表
    参数n为数列的长度
    返回包含前n个斐波那契数的列表
    """
    # 处理边缘情况
    if n <= 0:
        return []
    # 基本情况：第一个斐波那契数
    elif n == 1:
        return [1]
    # 基本情况：前两个斐波那契数
    elif n == 2:
        return [1, 1]
    # 递归情况：基于前n-1个元素的列表生成前n个元素的列表
    else:
        # 递归获取前n-1个斐波那契数的列表
        prev_list = fibonacci_list(n - 1)
        # 计算第n个斐波那契数（前两个数之和）并添加到列表
        next_num = prev_list[-1] + prev_list[-2]
        prev_list.append(next_num)
        return prev_list

# 测试函数
if __name__ == "__main__":
    print(fibonacci_list(1))   # 输出: [1]
    print(fibonacci_list(2))   # 输出: [1, 1]
    print(fibonacci_list(7))   # 输出: [1, 1, 2, 3, 5, 8, 13]
    print(fibonacci_list(10))  # 输出: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]